package 路径问题;

/**
 * @Date 2024/6/14 15:08
 * @description: 地下城游戏（状态表示等五个都是反的）
 * .               https://leetcode.cn/problems/dungeon-game/description/
 * @Author LittleNight
 */
public class likou174 {

    // 完全跟前面的题完全反过来了: 包括状态表示, 方程, 和填表顺序
    public int calculateMinimumHP(int[][] dungeon) {
        // ×××××××dp[i]状态表示: 从起点左上角到达（i，j） 位置的最小健康点数 这种找不出状态方程××××
        // dp[i]状态表示: 从（i，j） 位置到达终点所需的最小健康点数

        // 1.创建 dp表
        // 2.初始化
        // 3.填表
        // 4.返回值
        // 动态规划 这里的是二维, 所以时空都是O(M*N)
        int m = dungeon.length, n = dungeon[0].length;
        int[][] dp = new int[m + 1][n + 1];

        // 初始化， 新加的最右边一列和最下边一列
        // 都需要进行初始化为最大值 (因为求的是最小值, 默认的0有可能干扰结果)
        for(int i = 0; i <= m; i++) dp[i][n] = Integer.MAX_VALUE; //新增行
        for(int j = 0; j <= n; j++) dp[m][j] = Integer.MAX_VALUE; //新增列
        // dp[0][1] = dp[1][0] = 0; // 特殊处理边界
        dp[m][n - 1] = dp[m - 1][n] = 1;
        // 做好映射关系, 这里因为添加的是右下角的行和列, 所以不需要映射
        // 这里填的是 dp 表, 所以建议从(1,1) 开始. 也就是dp表多加了一行一列
        // 遍历的是 dp 表
        for(int i = m - 1; i >= 0; i--) { // 从xia往上每一行 和之前反过来了
            for(int j = n - 1; j >= 0; j--) { // 从you往左每一列
                // dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + dungeon[i - 1][j - 1]; 这是之前的写法, 这道题是反过来的
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                dp[i][j] = Math.max(1, dp[i][j]); //细节问题:防止血量有负数
            }
        }
        // return dp[m][n];
        return dp[0][0];
    }
}
